package com.hyper_yang.algorithmRecord.June;

import java.util.HashMap;

// 2025.06.05 按字典序排列最小的等效字符串
public class LeetCode_1061 {
    /*
    给出长度相同的两个字符串 s1和 s2还有一个字符串 baseStr。

    其中 s1[i]和 s2[i]是一组等价字符。
    举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。

    例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed",
    "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串
    利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。
     */
    // 并查集
    private int[] parent = new int[26];

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        // 初始化并查集
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        // 构建等价关系、构建并查集
        for (int i = 0; i < s1.length(); i++) {
            int char1 = s1.charAt(i) - 'a';
            int char2 = s2.charAt(i) - 'a';
            union(char1, char2);
        }
        // 构建最小等价字符串
        StringBuilder res = new StringBuilder();
        for (char c : baseStr.toCharArray()) {
            int index = (c - 'a');
            int smallC = find(index);
            res.append((char) ('a' + smallC));
        }
        return res.toString();
    }

    // 查找:
    public int find(int i) {
        if (parent[i] == i)
            return i;
        parent[i] = find(parent[i]);
        return parent[i];
    }

    // 合并:
    public void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        // 不在同一集合，合并
        if (rootA != rootB) {
            if (rootA < rootB)
                parent[rootB] = rootA;
            else
                parent[rootA] = rootB;
        }
    }

    public static void main(String[] args) {
        LeetCode_1061 solution = new LeetCode_1061();
        System.out.println(solution.smallestEquivalentString("parker", "morris", "parser")); // makkek
        System.out.println(solution.smallestEquivalentString("hello", "world", "hold")); // hdld
        System.out.println(solution.smallestEquivalentString("leetcode", "programs", "sourcecode")); // aauaaaaada
    }
}
// 等价字符遵循任何等价关系的一般规则：
// 自反性 ：'a' == 'a'
// 对称性 ：'a' == 'b' 则必定有 'b' == 'a'
// 传递性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'